翻訳と辞書 Words near each other ・ Ehrenfeld ・ Ehrenfeld (surname) ・ Ehrenfeld Group ・ Ehrenfeld, Cologne ・ Ehrenfeld, Pennsylvania ・ Ehrenfels ・ Ehrenfels Castle (Grisons) ・ Ehrenfels Castle (Hesse) ・ Ehrenfelser ・ Ehrenfest ・ Ehrenfest equations ・ Ehrenfest model ・ Ehrenfest paradox ・ Ehrenfest theorem ・ Ehrenfest–Tolman effect ・ Ehrenfeucht–Fraïssé game ・ Ehrenfeucht–Mostowski theorem ・ Ehrenfeucht–Mycielski sequence ・ Ehrenfried Günther Freiherr von Hünefeld ・ Ehrenfried Patzel ・ Ehrenfried Pfeiffer ・ Ehrenfried Rudolph ・ Ehrenfried Walther von Tschirnhaus ・ Ehrenfried-Oskar Boege ・ Ehrenfriedersdorf ・ Ehrengard ・ Ehrengard Schramm ・ Ehrengrab ・ Ehrenhausen ・ Ehrenkirchen Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Ehrenfeucht–Fraïssé game ： ウィキペディア英語版 Ehrenfeucht–Fraïssé game In the mathematical discipline of model theory, the Ehrenfeucht–Fraïssé game (also called back-and-forth games) is a technique for determining whether two structures are elementarily equivalent. The main application of Ehrenfeucht–Fraïssé games is in proving the inexpressibility of certain properties in first-order logic. Indeed, Ehrenfeucht–Fraïssé games provide a complete methodology for proving inexpressibility results for first-order logic. In this role, these games are of particular importance in finite model theory and its applications in computer science (specifically Computer Aided Verification and database theory), since Ehrenfeucht–Fraïssé games are one of the few techniques from model theory that remain valid in the context of finite models. Other widely used techniques for proving inexpressibility results, such as the compactness theorem, do not work in finite models. Ehrenfeucht–Fraïssé like games can also be defined for other logics, such as fixpoint logics and pebble games for finite variable logics; extensions are powerful enough to characterise definability in existential second-order logic. == Main idea == The main idea behind the game is that we have two structures, and two players (defined below). One of the players wants to show that the two structures are different, whereas the other player wants to show that they are somewhat similar (according to first-order logic). The game is played in turns and rounds; A round proceeds as follows: First the first player (Spoiler) chooses any element from one of the structures, and the other player chooses an element from the other structure. The other player's task is to always pick an element that is "similar" to the one that Spoiler chose. The second player (Duplicator) wins if there exists an isomorphism between the elements chosen in the two different structures. The game lasts for a fixed amount of steps ($\backslash gamma$) (an ordinal, but usually a finite number or $\backslash omega$). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ehrenfeucht–Fraïssé game」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.